算法设计------Priority_Queue实现

发表于 | 分类于 ，

Priority Queue

普通队列是一种先进先出（FIFO）的数据结构。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高优先先出（first in，lagest out）的行为特征。

实现方案

使用排序和数组可以简单的实现Priority Queue，插入到列表的时间复杂度为𝑂（𝑛），排序列表的时间复杂度为𝑂(𝑛log𝑛)。更优的方式是使用大顶堆（小顶堆），以大顶堆（小顶堆）实现的Priority Queue的出队、入队时间复杂度均为𝑂(log 𝑛)。

二进制堆

1. 堆中某个节点的值总是不大于或不小于其父节点的值（分别为大顶堆和小顶堆）。
2. 堆是一颗完全二叉树。

从二叉树角度来看大顶堆：

以数组存储该大顶堆：

子节点与父节点的关系:

p_left = p * 2;
p_right = p * 2 + 1;

调整堆（出队、入队操作）

入队

  1. 新元素插在树的末尾，如果树的最后一层已满，添加一层。
  2. 如果插入元素打破大顶堆（小顶堆）的结构，与其父节点交换。
  3. 重复第二步直至满足大顶堆（小顶堆）的结构。
入队时间复杂度： 𝑂(log 𝑛)

出队

  1. 交换根节点元素与最后一个元素，删除根节点元素（现在是最后一个元素）。
  2. 如果交换后的根节点打破大顶堆的结构，与其较大的孩子节点交换。
  3. 重复第二部直至满足大顶堆结构。
出队时间复杂度：𝑂(log 𝑛)

堆调整的可视化演示

堆 可视化演示

C语言实现

.h文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include "stdbool.h"

typedef struct priority_Queue_Node{
    int priority;//优先级
    int member;//数据域
}Priority_Queue_Node, * p_Priority_Node;

typedef struct priority_Queue{
    Priority_Queue_Node * nodeList;
    int length;//已分配内存长度
    int contentLength;//当前内容长度
}Priority_Queue, * p_Priority_Queue;

void InitPriorityQueue(p_Priority_Queue queue, int n);//初始化
bool Insert(p_Priority_Queue queue, int member,int priority);//入队
bool Empty(p_Priority_Queue queue);//判空
int RemoveTop(p_Priority_Queue queue);//出队
void travelPriorityQueue(p_Priority_Queue queue);//遍历

.c文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include "Priority_Queue.h"
#include "stdlib.h"
void adjustAfterInsert(p_Priority_Queue queue);
void adjustAfterRemove(p_Priority_Queue queue);
void swap(p_Priority_Node node1,p_Priority_Node node2);

void InitPriorityQueue(p_Priority_Queue queue, int n){
    Priority_Queue_Node * nodeList = malloc(sizeof(Priority_Queue_Node) * 2);
    if (nodeList == NULL) {
        printf("分配内存失败");
        exit(-1);
    }
    queue -> nodeList = nodeList;
    queue -> length = n;
    queue -> contentLength = 0;
}

bool CheckPriority(p_Priority_Queue queue, int priority){
    int position = 0;
    bool legal = true;
    while (position < queue -> contentLength) {
        if ((queue -> nodeList + position) -> priority == priority ) {
            printf("非法优先级");
            legal = false;
            break;
        }
        position ++;
    }
    return legal;
}

bool Insert(p_Priority_Queue queue, int member,int priority){
    if (!CheckPriority(queue, priority)) {
        return false;
    }
    
    if (queue -> length == queue -> contentLength) {
        queue -> length *= 2;
        queue -> nodeList = realloc(queue -> nodeList, sizeof(Priority_Queue_Node) * queue -> length);
        if (NULL == queue -> nodeList) {
            printf("分配内存失败");
            return false;
        }
        
    }
    int contentLength = queue -> contentLength;
    p_Priority_Node node = queue -> nodeList + contentLength;
    node -> member = member;
    node -> priority = priority;
    queue -> contentLength += 1;
    adjustAfterInsert(queue);
    
    printf("Insert %d with pri %d\n",member,priority);
    return true;
}

int RemoveTop(p_Priority_Queue queue){

    int return_val;
    if (Empty(queue)) {
        printf("Queue is empty");
        exit(-1);
    }else{

        p_Priority_Node pNode = queue -> nodeList;
        return_val = pNode -> member;
        swap(&(queue -> nodeList)[0], &(queue -> nodeList)[queue -> contentLength - 1]);
        queue -> contentLength -= 1;
        adjustAfterRemove(queue);
        printf("removeValue %d\n",return_val);
        return return_val;
    }
    return 1;
}

bool Empty(p_Priority_Queue queue){
    if (0 == queue -> contentLength) {
        return true;
    }else{
        return false;
    }
}

void travelPriorityQueue(p_Priority_Queue queue){
    if (Empty(queue)) {
        return;
    }
    int position = 0;
    while (position < queue -> contentLength) {
        printf("member --- %d with %d ---- priority\n",(queue -> nodeList + position) -> member , (queue -> nodeList + position) -> priority );
        position++;
    }
}

//入队后调整
void adjustAfterInsert(p_Priority_Queue queue){
    int insertPosition = queue -> contentLength - 1;
    while (insertPosition) {
        int swapPosition = insertPosition / 2;
        p_Priority_Node swapNode = &(queue -> nodeList)[swapPosition];
        p_Priority_Node insertNode = &(queue -> nodeList)[insertPosition];
        if (swapNode -> priority < insertNode -> priority) {
            swap(swapNode, insertNode);
            insertPosition = swapPosition;
        }else{
            break;
        }
    }
}

// 出队后调整
void adjustAfterRemove(p_Priority_Queue queue){
    int parent = 1;
    while (parent * 2 <= queue -> contentLength) {
        int left = parent * 2;
        int right = (parent * 2 + 1);
        if (right > queue -> contentLength) {
            right = queue -> contentLength;
        }
        p_Priority_Node parentNode = &(queue -> nodeList)[parent - 1];
        p_Priority_Node leftNode = &(queue -> nodeList)[left -1];
        p_Priority_Node rightNode = &(queue -> nodeList)[right -1];
        p_Priority_Node swapNode;
        if (leftNode -> priority >= rightNode -> priority) {
            parent = left;
            swapNode = leftNode;
        }else{
            parent = right;
            swapNode = rightNode;
        }
        if (swapNode -> priority >= parentNode -> priority) {
            swap(parentNode, swapNode);
        }else{
            break;
        }
    }
    
}

void swap(p_Priority_Node node1,p_Priority_Node node2){
    p_Priority_Node tempNode = malloc(sizeof(Priority_Queue_Node));
    
    if (NULL == tempNode) {
        printf("分配内存失败");
        exit(-1);
    }
    
    tempNode -> priority = node1 -> priority;
    tempNode -> member = node1 -> member;
    
    node1 -> member = node2 -> member;
    node1 -> priority = node2 -> priority;
    
    node2 -> priority = tempNode -> priority;
    node2 -> member = tempNode -> member;
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void testPriorityQueue(){
    Priority_Queue queue;
    InitPriorityQueue(&queue, 2);
    
    for (int i = 0; i < 20; i ++) {
        int pr = arc4random() % 100;
        int member = arc4random() % 100;
        Insert(&queue, member, pr);
        printf("================================================\n");
    }
    printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
    for (int i = 0; i < 20; i ++) {
        RemoveTop(&queue);
        travelPriorityQueue(&queue);
        printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
    }
}

备注

由于堆调整是不稳定的，同优先级元素出队顺序是不定的，这里不允许插入同优先级元素。

如果对你有帮助的话，Star✨下一吧！